package com.localking.algorithm.leetcode.array.string

/**
 * Given a sorted nums, remove the duplicates in-place such that each element appear only once and return the new length.
 * Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory
 *
 * Example 1:
 * Given nums = [1, 1, 2]
 * Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.
 * It doesn't matter what you leave beyond the returned length.
 *
 * Example 2:
 * Given nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
 * You function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3 and 4 respectively.
 * It doesn't matter what values are set beyond the returned length.
 *
 * Clarification:
 * Confused why the returned value is an integer but your answer is an array?
 * Note that the input array is passed by reference, which means modification to the input array will be known to the caller as well.
 * Internally you can think of this:
 *
 * // nums is passed in by reference. (i.e., without making a copy)
 * int len = removeDuplicates(nums)
 * // any modification to nums in you function would be known by the caller.
 * // using the length returned by your function, it prints the first len elements.
 * for(int i = 0; i < len; i++) {
 *  print(nums[i]);
 * }
 * @author jinbo
 */
object RemoveDuplicates {
  def main(args: Array[String]): Unit = {
    val nums = Array(1, 1, 2)
    val length = removeDuplicates(nums)
    println(s"nums's length is $length")
    for(i <- 0 until length) {
      println(nums(i))
    }
  }

  def removeDuplicates(nums: Array[Int]): Int = {
    if(nums.length <= 1) {
      return nums.length
    }
    var firstIndex = 0
    var length = 1
    for(secondIndex <- 1 until nums.length) {
      if(nums(secondIndex) != nums(firstIndex)) {
        nums.update(length, nums(secondIndex))
        firstIndex = secondIndex
        length += 1
      }
    }
    length
  }
}
